오일러 파이 함수

1. 개요 [편집]

오일러 파이 함수(Euler phi function)는 특수함수의 하나로, 정의는 다음과 같다.

\displaystyle \phi(n) \equiv \sum_{m=1}^{n} (\bold{1}_{\{1\}} \circ \gcd)(m,\,n)\quad

(

n \in \mathbb{N}

)

위에서

\gcd

는 최대공약수,

\bold{1}_{\{1\}}

는 서로소만을 취하기 위한 1만을 원소로 갖는 집합의 판별 함수이다.

이름대로 레온하르트 오일러가 정의한 함수다. 정의에서 보듯, 특정 수 이하의 서로소의 개수를 구하는 데 쓰인다. 서로소일 경우에만 값이 증가하므로, 이 함수는 계단함수다.

몇가지 특수한 성질이 존재하는데, 그 중 하나는 서로소인 서로 다른 두 수 $a,b$ 라는 조건을 걸 경우, 정수론적 함수[1]의 성질을 지니고 있다는 점이다. 즉, 다음과 같다.

만약

\gcd(a,\,b)=1

이라면,

\phi(ab)=\phi(a)\phi(b)

또, 임의의 소수 $p$ 에 대하여,

\phi(p^n)

은

1\leq a\leq p^n

인

a

중

p^n

과 서로소인 수의 개수이며,

p^n

는

p

만을 소인수로 가지기 때문에 자동적으로

\displaystyle \phi(p^n)=p^{n}-\frac{p^{n}}{p}=p^{n}\left(1-\frac{1}{p}\right)

가 된다.

이 두 성질을 조합하면, 오일러 파이 함수는 다음과 같은 수단으로 구할 수 있다는 것을 알 수 있다.

\displaystyle a=\prod_{i=1}^n p_{i}^{k_{i}}

의 형태로 소인수분해할 수 있다고 두면

\displaystyle \phi(a)=\phi\left(\prod_{i=1}^n p_{i}^{k_{i}}\right)=\prod_{i=1}^n \phi(p_{i}^{k_{i}})=\prod_{i=1}^n \left[p_{i}^{k_{i}}\left(1-\frac{1}{p_i}\right)\right]

즉,

\displaystyle \phi(n)= n \prod_{p|n}(1-\frac {1}{p})

(단,

p

는 소수)

또한, 뫼비우스 반전 공식(Möbius inversion formula)이 적용되기에, 뫼비우스 함수

\mu

[2]를 이용하면 다음이 성립한다.

\displaystyle\phi(n)=\sum_{n\mid d}\mu\left(\frac{n}{d}\right)d

[1] 정의역과 치역이 모두 정수, 혹은 정수의 부분집합인 함수 중에서

f(ab)=f(a)f(b)

라는 성질을 지닌 함수를 의미한다.[2] 주어진 수가 소수의 거듭제곱을 인수로 가지고 있는지를 판정하는 함수다. 거듭제곱을 인수로 가지고 있다면 0, 거듭제곱이 없다면 소인수의 개수, 즉 소인수 계량 함수를 따져서

\mu(n)=\left(-1\right)^{\omega(n)}

가 된다.